En
Teoría de la complejidad computacional,
BQP representa la clase de algoritmos que pueden ser resueltos en un
computador cuántico en
tiempo polinómico con un margen de error promedio inferior a 1/4.
Dicho de otra forma, existe un
algoritmo de computación cuántica cuya cota superior en tiempo es polinómica para resolver ese problema, tal que la probabilidad de obtener una respuesta equivocada es menor de 25\%.
El nivel de error de 1/4 es arbitrario, cualquier valor real k tal que 0 < k < 1/2 podría ser utilizado sin cambiar el conjunto
BQP. La idea es que con una pequeña probabilidad de error se corre el algoritmo un número suficiente de veces se llega a una probabilidad exponencialmente pequeña de que la mayoría de las corridas sean erróneas.